<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<html><head>
<!--Converted with LaTeX2HTML 98.1 release (February 19th, 1998)
originally by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds
* revised and updated by:  Marcus Hennecke, Ross Moore, Herb Swan
* with significant contributions from:
  Jens Lippmann, Marek Rouchal, Martin Wilck and others -->


<title>Prime Ring Problem</title>
<meta name="description" content="Prime Ring Problem">
<meta name="keywords" content="htmlatex">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<link rel="STYLESHEET" href="acm-00524_files/htmlatex.css">
</head><body bgcolor="#ffffff" lang="EN">

<h1><br clear="all"><center><table bgcolor="#0060f0"><tbody><tr><td><b><font size="5" color="#c0ffff">&nbsp;<a name="SECTION0001000000000000000000">
Prime Ring Problem</a>&nbsp;</font></b></td></tr></tbody></table></center>
</h1>

<p>
A ring is composed of n (even number) circles as shown in diagram. Put natural
numbers 
<!-- MATH: $1, 2, \dots, n$ -->
<img src="acm-00524_files/524img1.gif" alt="$1, 2, \dots, n$" width="79" align="middle" border="0" height="30">
into each circle separately, and the sum of numbers in two adjacent circles
should be a prime. 

</p><p>
</p><div align="center">
<img src="acm-00524_files/p524.gif">
</div>

<p>

</p><p>
<br>

<b>Note:</b> the number of first circle should always be 1.

</p><p>

</p><h2><font color="#0070e8"><a name="SECTION0001001000000000000000">
Input</a>&nbsp;</font>
</h2>
<i>n (0 &lt; n &lt;= 16)</i> 

<!--
(
< MATH: $0 < n \le 20$ >
<IMG
 WIDTH="88" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
 SRC="524img2.gif"
 ALT="$0 < n \le 20$">)
-->

<p>

</p><h2><font color="#0070e8"><a name="SECTION0001002000000000000000">
Output</a>&nbsp;</font>
</h2>
The output format is shown as sample below. Each row represents a series
of circle numbers in the
ring beginning from 1 clockwisely and anticlockwisely. The order of numbers
must satisfy the above requirements.

<p>

</p><p>
<br>
You are to write a program that completes above process.

</p><p>

</p><h2><font color="#0070e8"><a name="SECTION0001003000000000000000">
Sample Input</a>&nbsp;</font>
</h2>
<pre>6
8
</pre>

<p>

</p><h2><font color="#0070e8"><a name="SECTION0001004000000000000000">
Sample Output</a>&nbsp;</font>
</h2>
<pre>Case 1:
1 4 3 2 5 6
1 6 5 2 3 4

Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
</pre>

<p>

</p><p>
<br></p><hr>
<address>
<i>Miguel A. Revilla</i>
<br><i>1999-01-11</i>
</address>
</body></html>